package 第二章数据结构.Trie字典树.id835Trie字符串统计;

/**
 * 构建一个字典树集合，可以在O(N)的时间内查询，集合中出现的字符串或前缀的次数
 */

import java.util.Scanner;

public class Main {
    static TireNode root = new TireNode();
    public static void main(String[]args){
        Scanner scanner = new Scanner (System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        while (n-- > 0){
            String s = scanner.nextLine();
            String[] op = s.split(" ");
            if(op[0].equals("I")){
                insert(op[1]);
            }else if(op[0].equals("Q")){
                int ret  = query(op[1]);
                System.out.println(ret);
            }
        }
    }
    //字典树节点
    static class TireNode{
        TireNode[] sons = new TireNode[26];
        boolean isEnd = false;
        int cnt;
    }

    static void insert(String s){
        TireNode cur = root;

        for(int i = 0;i<s.length();i++){
            int k = s.charAt(i)-'a';
            //如果没有就创建节点
            if(cur.sons[k] == null){
                cur.sons[k] = new TireNode();
            }
            cur = cur.sons[k];
        }
        cur.isEnd = true;
        cur.cnt++;
    }
    static int query(String s){
        TireNode cur = root;
        for(int i = 0;i<s.length();i++){
            int k =  s.charAt(i)- 'a';
            //如果不存在
            if(cur.sons[k] == null){
                return 0;
            }else{
                cur = cur.sons[k];
            }
        }
        return cur.cnt;
    }
}
